//#include<stdio.h>
//#include <windows.h> //ע���������ͷ�ļ�
//
//#define ture 1
//#define ll long long
//#define maxn 10000
//#define maxn 100000
//
//#define maxn 100000
//ll compare, move;
//ll length = maxn;
//ll a[maxn + 10];
//ll dlta[10] = {5, 3, 1};
//
//ֱ�Ӳ�������
//void sort() {
//    int i, j;
//    for (i = 2; i <= length; i++) {
//        compare++;
//        if (a[i] < a[i - 1]) {
//            a[0] = a[i];
//            a[i] = a[i - 1];
//            for (j = i - 2; a[0] < a[j]; j--) {
//                a[j + 1] = a[j];
//                compare++;
//                move++;
//            }
//            a[j + 1] = a[0];
//        }
//    }
//}
//
//�۰��������
//void Insort() {
//    int i, j, m, low, high;
//    for (i = 2; i <= length; i++) {
//        a[0] = a[i];
//        low = 1;
//        high = i - 1;
//        while (low <= high) {
//            compare++;
//            m = (low + high) / 2;
//            if (a[0] < a[m]) high = m - 1;
//            else low = m + 1;
//        }
//        for (j = i - 1; j >= high + 1; --j) {
//            a[j + 1] = a[j];
//            move++;
//        }
//        a[high + 1] = a[0];
//    }
//}
//
//ϣ������
//void ShellInsert(int dk) {
//    int i, j;
//    //��˳���L����һ������Ϊdk��Shell����dkΪ��������
//    for (i = dk + 1; i <= length; ++i) {//��ʼ��a[i] �������������ӱ�
//        compare++;
//        if (a[i] < a[i - dk]) {
//            a[0] = a[i];//�ݴ���a[0]
//            for (j = i - dk; j > 0 && (a[0] < a[j]); j = j - dk) {
//                a[j + dk] = a[j];//�ؼ��ֽϴ�ļ�¼���ӱ��к���
//                compare++;
//                move++;
//            }
//            a[j + dk] = a[0];//�ڱ��˽���ʱ��a[i]���뵽��ȷλ��
//        }
//    }
//}
//
//
//void ShellSort() {
//    int k;
//����������dlta[0��t-1]��˳���L��Shell����
//    for (k = 0; k < 3; ++k)
//        ShellInsert(dlta[k]);//����Ϊdlta[k]��һ�˲������� ��
//}
//
//ð������
//void MPsort() {
//    int i, j, t;
//    for (j = 1; j <= length - 1; j++) {
//        for (i = 0; i <= length - j - 1; i++) {
//            compare++;
//            if (a[i] > a[i + 1]) {
//                t = a[i];
//                a[i] = a[i + 1];
//                a[i + 1] = t;
//                move++;
//            }
//        }
//    }
//}
//
//��������
//int Partition(int low, int high) {
//    a[0] = a[low];
//    int key = a[low];
//    while (low < high) {
//        compare++;
//        while (low < high && a[high] >= key) {
//            --high;
//            compare++;
//        }
//        a[low] = a[high];
//        move++;
//        while (low < high && a[low] <= key) {
//            ++low;
//            compare++;
//        }
//        a[high] = a[low];
//        move++;
//    }
//    a[low] = a[0];
//    return low;
//}
//
//void QSort(int low, int high) {
//    int mid;
//    compare++;
//    if (low < high) {
//        mid = Partition(low, high);
//        QSort(low, mid - 1);
//        QSort(mid + 1, high);
//    }
//}
//
//��ѡ������
//void SelectSort() {
//    int i, j, t;
//    for (i = 1; i < length; ++i) { //��a[i..L.length] ��ѡ����С�ļ�¼
//        int k = i;
//        for (j = i + 1; j <= length; j++) {
//            compare++;
//            if (a[j] < a[k]) k = j;
//        }
//        if (k != i) {
//            t = a[i];
//            a[i] = a[k];
//            a[k] = t;
//            move++;
//        }
//    }
//}
//
//������
//void HeapAdjust(int s, int m) {
//    int i, j, rc;
//    rc = a[s];
//    //��key�ϴ�ĺ��ӽ������ɸѡ
//    for (j = 2 * s; j <= m; j *= 2) {
//        compare++;
//        if (j < m && a[j] < a[j + 1]) ++j;
//        compare++;
//        if (rc >= a[j]) break;
//        a[s] = a[j];
//        s = j;
//        move++;
//    }
//    a[s] = rc;
//}
//
//void CreatHeap() {
//    int n, i;
//    n = length;
//    //��������HeapAdjust()����
//    for (i = n / 2; i > 0; --i)
//        HeapAdjust(i, n);
//}
//
//void HeapSort() {
//    int i, x;
//    CreatHeap();
//    for (i = length; i > 1; --i) {
//        x = a[1];
//        a[1] = a[i];
//        a[i] = x;
//        move++;
//        HeapAdjust(1, i - 1);
//    }
//}
//
//�鲢����
//void Merge(ll S[], ll T[], ll low, ll mid, ll high) {
//    ll i, j, k;
//    i = low, j = mid + 1, k = low;
//    while (i <= mid && j <= high) {
//        compare++;
//        if (S[i] <= S[j]) T[k++] = S[i++];
//        else T[k++] = S[j++];
//    }
//    while (i <= mid) {
//        T[k++] = S[i++];
//        move++;
//    }
//    while (j <= high) {
//        T[k++] = S[j++];
//        move++;
//    }
//}
//
//void Msort(ll S[], ll T[], ll low, ll high) {
//    ll R[maxn + 10];
//    compare++;
//    if (low == high) {
//        T[low] = S[low];
//        move++;
//    } else {
//        ll mid = (low + high) / 2;
//        Msort(S, R, low, mid);
//        Msort(S, R, mid + 1, high);
//        Merge(R, T, low, mid, high);
//    }
//}
//
//int main() {
//    //���������ṹ�壬����¼��ʼ�ͽ���ʱ��
//    DWORD start, stop;
//    int i;
//    while (ture) {
//        for (i = 1; i <= length; i++) {//�������maxn������
//            a[i] = rand();
//        }
//        int t;
//        move = 0, compare = 0;
//        puts("��������������ѡ������ʽ������������");
//        puts("1 ֱ�Ӳ�������");
//        puts("2 �۰��������");
//        puts("3 ϣ������");
//        puts("4 ð������");
//        puts("5 ��������");
//        puts("6 ѡ������");
//        puts("7 ������");
//        puts("8 �鲢����");
//        scanf("%d", &t);
//        switch (t) {
//            case 1 : {
//                //��ʼ��ʱ
//                start = GetTickCount();
//                sort();
//                //������ʱ
//                stop = GetTickCount();
//                break;
//            }
//            case 2 : {
//                //��ʼ��ʱ
//                start = GetTickCount();
//                Insort();
//                //������ʱ
//                stop = GetTickCount();
//                break;
//            }
//            case 3 : {
//                //��ʼ��ʱ
//                start = GetTickCount();
//                ShellSort();
//                //������ʱ
//                stop = GetTickCount();
//                break;
//            }
//            case 4: {
//                //��ʼ��ʱ
//                start = GetTickCount();
//                MPsort();
//                //������ʱ
//                stop = GetTickCount();
//                break;
//            }
//            case 5: {
//                //��ʼ��ʱ
//                start = GetTickCount();
//                QSort(1, length);
//                //������ʱ
//                stop = GetTickCount();
//                break;
//            }
//            case 6: {
//                //��ʼ��ʱ
//                start = GetTickCount();
//                SelectSort();
//                //������ʱ
//                stop = GetTickCount();
//                break;
//            }
//            case 7: {
//                //��ʼ��ʱ
//                start = GetTickCount();
//                HeapSort();
//                //������ʱ
//                stop = GetTickCount();
//                break;
//            }
//            case 8: {
//                //��ʼ��ʱ
//                start = GetTickCount();
//                Msort(a, a, 1, length);
//                //������ʱ
//                stop = GetTickCount();
//                break;
//            }
//        }
//        for (i = 1; i <= length; i++) {//���������ɵ�maxn������
//            printf("%d ", a[i]);
//        }
//        printf("\n");
//        //����ʱ������ӡ
//        printf("time: %lld ms\n", stop - start);
//        printf("�Ƚϴ�����%lld\n", compare);
//        printf("�ƶ�������%lld\n", move);
//    }
//    return 0;
//}
